package leetcode.backtrace.common;

import leetcode.array.common.ArrayUtils;
import leetcode.tree.common.TreeNode;
import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class BackTraceUtils {
    /**
     * 0 <= digits.length <= 4
     * digits[i] 是范围 ['2', '9'] 的一个数字。
     *
     * @param digits
     * @return
     */
    public static List<String> letterCombinations(String digits) {
        char[][] numToChar = {
                {'a', 'b', 'c'},
                {'d', 'e', 'f'},
                {'g', 'h', 'i'},
                {'j', 'k', 'l'},
                {'m', 'n', 'o'},
                {'p', 'q', 'r', 's'},
                {'t', 'u', 'v'},
                {'w', 'x', 'y', 'z'}
        };
        List<String> result = new ArrayList<>();
        if (digits.length() == 0) {
            return result;
        }
        int curIndex = 0;
        // digits 长度不大于4
        char[] curResult = new char[digits.length()];
        solveLetterCombinations(digits.toCharArray(), numToChar, result, curIndex, curResult);
        return result;
    }

    private static void solveLetterCombinations(char[] digits, char[][] numToChar, List<String> result, int curIndex, char[] curResult) {
        if (curIndex == digits.length && curResult.length > 0) {
            result.add(String.valueOf(curResult));
            return;
        }
        char digit = digits[curIndex];
        int num = Integer.parseInt(String.valueOf(digit));
        char[] chars = numToChar[num - 2];
        for (char aChar : chars) {
            curResult[curIndex] = aChar;
            solveLetterCombinations(digits, numToChar, result, curIndex + 1, curResult);
            curResult[curIndex] = '0';
        }
    }

    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) {
            return result;
        }
        int curIndex = 0;
        Stack<String> stack = new Stack<>();
        char[] curResult = new char[n * 2];
        char[] parenthesis = {'(', ')'};
        solveGenerateParenthesis(n, curIndex, stack, curResult, result, parenthesis);
        return result;
    }

    private static void solveGenerateParenthesis(int n, int curIndex, Stack<String> stack, char[] curResult, List<String> result, char[] parenthesis) {
        if (curIndex == 2 * n && curResult.length > 0) {
            result.add(String.valueOf(curResult));
            return;
        }
        for (char c : parenthesis) {
            // 检查当前选项
            boolean checkResult = checkParenthesis(c, stack, curResult, n);
            if (!checkResult) {
                continue;
            }
            // 做出选择
            curResult[curIndex] = c;
            // 执行选择
            solveGenerateParenthesis(n, curIndex + 1, stack, curResult, result, parenthesis);
            // 撤销选择
            curResult[curIndex] = '0';
        }
    }

    private static boolean checkParenthesis(char parenthesis, Stack<String> stack, char[] curResult, int n) {
        if (parenthesis == '(') {
            int leftTime = 0;
            for (char c : curResult) {
                if (c == '(') {
                    leftTime++;
                }
            }
            if (leftTime < n) {
                stack.push(String.valueOf(parenthesis));
                return true;
            }
        } else if (parenthesis == ')') {
            stack.clear();
            for (char c : curResult) {
                if (c == '(') {
                    stack.push("(");
                } else if (c == ')') {
                    if (stack.isEmpty()) {
                        return false;
                    }
                    stack.pop();
                }
            }
            return stack.size() > 0;
        }
        return false;
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int curIndex = 0;
        List<Integer> curList = new ArrayList<>();
        solveCombinationSum(candidates, target, result, curIndex, curList);
        return result;
    }

    private static void solveCombinationSum(int[] candidates, int target, List<List<Integer>> result, int curIndex, List<Integer> curList) {
        if (listToSum(curList) == target) {
            result.add(new ArrayList<>(curList));
            return;
        }
        for (int i = curIndex; i < candidates.length; i++) {
            if (listToSum(curList) + candidates[i] > target) {
                continue;
            }
            curList.add(candidates[i]);
            solveCombinationSum(candidates, target, result, i, curList);
            curList.remove(curList.size() - 1);
        }
    }

    public static int listToSum(List<Integer> curList) {
        int sum = 0;
        for (Integer integer : curList) {
            sum = sum + integer;
        }
        return sum;
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int sum = arrayToSum(candidates);
        if (sum < target) {
            return result;
        }
        int curIndex = 0;
        List<Integer> curList = new ArrayList<>();
        Arrays.sort(candidates);
        solveCombinationSum2(candidates, target, curList, curIndex, result);
        return result;
    }

    private static int arrayToSum(int[] candidates) {
        int sum = 0;
        for (int candidate : candidates) {
            sum = sum + candidate;
        }
        return sum;
    }

    private static void solveCombinationSum2(int[] candidates, int target, List<Integer> curList, int curIndex, List<List<Integer>> result) {
        if (listToSum(curList) == target) {
            result.add(new ArrayList<>(curList));
            return;
        }
        Integer lastRemoved = null;
        for (int i = curIndex; i < candidates.length; i++) {
            // candidates 排序后，某个候选值已经超了，后面所有的数都会超，而且也解决了组合重复的问题
            if (listToSum(curList) + candidates[i] > target) {
                break;
            }
            if (lastRemoved != null && candidates[i] == lastRemoved) {
                continue;
            }
            curList.add(candidates[i]);
            solveCombinationSum2(candidates, target, curList, i + 1, result);
            lastRemoved = curList.get(curList.size() - 1);
            curList.remove(curList.size() - 1);
        }
    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        List<Integer> curList = new ArrayList<>();
        boolean[] selectedFlag = new boolean[nums.length];
        solvePermute(nums, result, curList, selectedFlag);
        return result;
    }

    private static void solvePermute(int[] nums, List<List<Integer>> result, List<Integer> curList, boolean[] selectedFlag) {
        if (curList.size() == nums.length) {
            result.add(new ArrayList<>(curList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (selectedFlag[i]) {
                continue;
            }
            // 类似于入栈
            curList.add(nums[i]);
            selectedFlag[i] = true;
            solvePermute(nums, result, curList, selectedFlag);
            // 类似于出栈
            curList.remove(curList.size() - 1);
            selectedFlag[i] = false;
        }
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        List<Integer> curList = new ArrayList<>();
        boolean[] selectedFlag = new boolean[nums.length];
        solvePermuteUnique(nums, result, curList, selectedFlag);
        return result;

    }

    private static void solvePermuteUnique(int[] nums, List<List<Integer>> result, List<Integer> curList, boolean[] selectedFlag) {
        if (curList.size() == nums.length) {
            result.add(new ArrayList<>(curList));
            return;
        }
        Integer lastRemoved = null;
        for (int i = 0; i < nums.length; i++) {
            if (selectedFlag[i]) {
                continue;
            }
            if (lastRemoved != null && nums[i] == lastRemoved) {
                continue;
            }
            curList.add(nums[i]);
            selectedFlag[i] = true;
            solvePermuteUnique(nums, result, curList, selectedFlag);
            lastRemoved = curList.get(curList.size() - 1);
            curList.remove(curList.size() - 1);
            selectedFlag[i] = false;
        }

    }

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] chessBoard = new char[n][n];
        initCharArray(chessBoard, '.');

        int row = 0;
        int col = 0;

        char[] queen = {'Q', '.'};
        int queenNum = 0;
        solveNQueens(row, col, chessBoard, result, n, queen, queenNum);
        return result;
    }

    private static void initCharArray(char[][] chessBoard, char c) {
        for (char[] chars : chessBoard) {
            Arrays.fill(chars, c);
        }
    }

    private static void solveNQueens(int row, int col, char[][] chessBoard, List<List<String>> result, int n, char[] queen, int queenNum) {
        if (row == n - 1 && col == n) {
            if (queenNum == n) {
                List<String> curResult = charArrayToStringList(chessBoard);
                result.add(curResult);
            }
            return;
        }
        if (col == n) {
            boolean chechResult = checkQExist(chessBoard, row, n);
            if (!chechResult) {
                return;
            }
            col = 0;
            row++;
        }

        for (char c : queen) {
            if (c == 'Q') {
                boolean chechResult = checkQ(row, col, chessBoard, n, queenNum + 1);
                if (!chechResult) {
                    continue;
                }
                // 选择皇后
                chessBoard[row][col] = 'Q';
                // 进入下一个位置
                solveNQueens(row, n, chessBoard, result, n, queen, queenNum + 1);
                chessBoard[row][col] = '.';
            } else {
                solveNQueens(row, col + 1, chessBoard, result, n, queen, queenNum);
            }

        }
    }

    private static boolean checkQExist(char[][] chessBoard, int row, int n) {
        for (int i = 0; i < n; i++) {
            if (chessBoard[row][i] == 'Q') {
                return true;
            }
        }
        return false;
    }

    private static boolean checkQ(int row, int col, char[][] chessBoard, int n, int queenNum) {
        // 检查皇后数量
        if (queenNum > n) {
            return false;
        }
        // 检查行或者列
        for (int i = 0; i < n; i++) {
            if (chessBoard[row][i] == 'Q' || chessBoard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查斜线
        int[] xDir = {1, 1, -1, -1};
        int[] yDir = {1, -1, 1, -1};
        for (int i = 0; i < 4; i++) {
            int x = row;
            int y = col;
            while (x < n && x >= 0 && y < n && y >= 0) {
                if (chessBoard[x][y] == 'Q') {
                    return false;
                }
                x = x + xDir[i];
                y = y + yDir[i];
            }
        }
        return true;
    }

    private static List<String> charArrayToStringList(char[][] charArray) {
        List<String> curList = new ArrayList<>();
        for (char[] chars : charArray) {
            StringBuilder s = new StringBuilder();
            for (char c : chars) {
                s.append(c);
            }
            curList.add(s.toString());
        }
        return curList;
    }

    public static int totalNQueens(int n) {
        List<List<String>> result = solveNQueens(n);
        return result.size();
    }

    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        int curIndex = 1;
        Stack<Integer> stack = new Stack<>();
        solveCombine(result, curIndex, n, k, stack);
        return result;
    }

    private static void solveCombine(List<List<Integer>> result, int curIndex, int n, int k, Stack<Integer> stack) {
        if (stack.size() == k) {
            result.add(new ArrayList<>(stack));
            return;
        }
        for (int i = curIndex; i <= n; i++) {
            stack.push(i);
            solveCombine(result, i + 1, n, k, stack);
            stack.pop();
        }
    }

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] choices = {false, true};
        List<Integer> curList = new ArrayList<>();
        int curIndex = 0;
        solveSubsets(nums, result, choices, curIndex, curList);
        return result;
    }

    private static void solveSubsets(int[] nums, List<List<Integer>> result, boolean[] choices, int curIndex, List<Integer> curList) {
        if (curIndex == nums.length) {
            result.add(new ArrayList<>(curList));
            return;
        }
        for (boolean choice : choices) {
            if (choice) {
                curList.add(nums[curIndex]);
                solveSubsets(nums, result, choices, curIndex + 1, curList);
                curList.remove(curList.size() - 1);
            } else {
                solveSubsets(nums, result, choices, curIndex + 1, curList);
            }
        }
    }

    public static boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        char[] words = word.toCharArray();
        int m = board.length;
        int n = board[0].length;
        boolean[][] selectedFlag = new boolean[m][n];
        initBooleanArray(selectedFlag);
        Stack<String> stack = new Stack<>();
        int curIndex = 0;
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                if (board[row][col] != words[0]) {
                    continue;
                }
                stack.push(String.valueOf(board[row][col]));
                selectedFlag[row][col] = true;
                boolean result = solveExist(board, words, selectedFlag, row, col, stack, curIndex + 1);
                if (result) {
                    return true;
                }
                stack.pop();
                selectedFlag[row][col] = false;
            }
        }
        return false;
    }

    private static void initBooleanArray(boolean[][] selectedFlag) {
        for (boolean[] booleans : selectedFlag) {
            Arrays.fill(booleans, false);
        }
    }

    private static boolean solveExist(char[][] board, char[] words, boolean[][] selectedFlag, int row, int col, Stack<String> stack, int curIndex) {
        if (stack.size() == words.length) {
            return true;
        }
        int[] xDir = {0, 1, 0, -1};
        int[] yDir = {1, 0, -1, 0};
        for (int i = 0; i < 4; i++) {
            int x = row + xDir[i];
            int y = col + yDir[i];
            if (checkPos(x, y, board) && board[x][y] == words[curIndex] && !selectedFlag[x][y]) {
                stack.push(String.valueOf(board[x][y]));
                selectedFlag[x][y] = true;
                boolean exist = solveExist(board, words, selectedFlag, x, y, stack, curIndex + 1);
                if (exist) {
                    return true;
                }
                stack.pop();
                selectedFlag[x][y] = false;
            }
        }
        return false;
    }

    private static boolean checkPos(int x, int y, char[][] board) {
        int m = board.length;
        int n = board[0].length;
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    public static List<Integer> grayCode(int n) {
        if (n == 1) {
            List<Integer> result = new ArrayList<>();
            result.add(0);
            result.add(1);
            return result;
        }
        List<Integer> result = grayCode(n - 1);
        int halfSize = result.size();
        for (int i = halfSize - 1; i >= 0; i--) {
            result.add(result.get(i) | (1 << (n - 1)));
        }
        return result;
    }

    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> curList = new ArrayList<>();
        int curIndex = 0;
        Map<Integer, Integer> numTimeMap = countFrequence(nums);
        Set<Integer> keySet = numTimeMap.keySet();
        List<Integer> keys = new ArrayList<>(keySet);
        keys.sort(Comparator.comparingInt(o -> o));
        solveSubsetsWithDup(keys, result, curIndex, curList, numTimeMap);
        return result;
    }

    private static void solveSubsetsWithDup(List<Integer> keys, List<List<Integer>> result, int curIndex, List<Integer> curList, Map<Integer, Integer> numTimeMap) {
        if (curIndex == numTimeMap.size()) {
            result.add(new ArrayList<>(curList));
            return;
        }
        for (int i = 0; i <= numTimeMap.get(keys.get(curIndex)); i++) {
            int j = i;
            while (j > 0) {
                curList.add(keys.get(curIndex));
                j--;
            }
            solveSubsetsWithDup(keys, result, curIndex + 1, curList, numTimeMap);
            j = i;
            while (j > 0) {
                curList.remove(curList.size() - 1);
                j--;
            }
        }
    }

    private static Map<Integer, Integer> countFrequence(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.merge(num, 1, Integer::sum);
        }
        return freq;
    }


    public static List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        List<String> curIP = new ArrayList<>();
        int beforeDot = 0;
        solveRestoreIpAddresses(s, result, curIP, beforeDot);
        return result;
    }

    private static void solveRestoreIpAddresses(String s, List<String> result, List<String> curIP, int beforeDot) {
        if (curIP.size() == 4) {
            result.add(String.join(".", curIP));
            return;
        }
        if (curIP.size() == 3) {
            getIpPart(s, result, curIP, beforeDot, s.length());
        } else {
            int loopEnd = Math.min(beforeDot + 3, s.length() - 1);
            for (int i = beforeDot + 1; i <= loopEnd; i++) {
                getIpPart(s, result, curIP, beforeDot, i);
            }
        }
    }

    private static void getIpPart(String s, List<String> result, List<String> curIP, int beforeDot, int end) {
        String curPart = s.substring(beforeDot, end);
        boolean checkResult = checkPart(curPart);
        if (checkResult) {
            curIP.add(curPart);
            solveRestoreIpAddresses(s, result, curIP, end);
            curIP.remove(curIP.size() - 1);
        }
    }

    private static boolean checkPart(String curPart) {
        if (curPart.length() == 0 || curPart.length() > 3) {
            return false;
        }
        if (curPart.length() > 1 && curPart.charAt(0) == '0') {
            return false;
        }
        for (int i = 0; i < curPart.length(); i++) {
            if (curPart.charAt(i) < '0' || curPart.charAt(i) > '9') {
                return false;
            }
        }
        return Integer.parseInt(curPart) <= 255 && Integer.parseInt(curPart) >= 0;
    }

    public static List<TreeNode> generateTrees(int n) {
        return solveGenerateTrees(1, n);
    }

    public static List<TreeNode> solveGenerateTrees(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }
        // 枚举可行根节点
        for (int i = start; i <= end; i++) {
            // 获得所有可行的左子树集合
            List<TreeNode> leftTrees = solveGenerateTrees(start, i - 1);
            // 获得所有可行的右子树集合
            List<TreeNode> rightTrees = solveGenerateTrees(i + 1, end);
            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode currTree = new TreeNode(i);
                    currTree.left = left;
                    currTree.right = right;
                    allTrees.add(currTree);
                }
            }
        }
        return allTrees;
    }

    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        constructPaths(root, "", paths);
        return paths;
    }

    public static void constructPaths(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuilder pathSB = new StringBuilder(path);
            pathSB.append(root.val);
            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                paths.add(pathSB.toString());  // 把路径加入到答案中
            } else {
                pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 3) {
            if (Arrays.stream(nums).sum() == 0) {
                List<Integer> list = ArrayUtils.intArrayToList(nums);
                result.add(list);
            }
            return result;
        }
        Arrays.sort(nums);
        int index = 0;
        List<Integer> curResult = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        solveThreeSum(result, index, curResult, nums, list);
        return result;
    }

    private static void solveThreeSum(List<List<Integer>> result, int index, List<Integer> curResult, int[] nums, List<Integer> list) {
        if (curResult.size() == 3) {
            if (curResult.stream().mapToInt(Integer::intValue).sum() == 0) {
                result.add(new ArrayList<>(curResult));
            }
            return;
        }
        if (index == nums.length) {
            return;
        }
        if (list.isEmpty() || list.get(0) != nums[index]) {
            // 选择
            curResult.add(nums[index]);
            solveThreeSum(result, index + 1, curResult, nums, list);
            list.clear();
            list.add(curResult.get(curResult.size() - 1));
            curResult.remove(curResult.size() - 1);
        }
        // 不选择
        solveThreeSum(result, index + 1, curResult, nums, list);
    }

    public static int uniquePaths(int m, int n) {
        int curX = 0;
        int curY = 0;
        int[] result = new int[1];
        solveUniquePaths(curX, curY, m, n, result);
        return result[0];
    }

    private static void solveUniquePaths(int curX, int curY, int m, int n, int[] result) {
        if (curX == n - 1 && curY == m - 1) {
            result[0]++;
            return;
        }
        if (curX < n - 1) {
            solveUniquePaths(curX + 1, curY, m, n, result);
        }
        if (curY < m - 1) {
            solveUniquePaths(curX, curY + 1, m, n, result);
        }
    }

    public static List<String> readBinaryWatch(int turnedOn) {
        int[] time = {8, 4, 2, 1, 32, 16, 8, 4, 2, 1};
        List<Integer> curTime = new ArrayList<>();
        int curIndex = 0;
        List<String> result = new ArrayList<>();
        getBinaryTime(turnedOn, time, curTime, curIndex, result);
        return result;
    }

    private static void getBinaryTime(int turnedOn, int[] time, List<Integer> curTime, int curIndex, List<String> result) {
        if (turnedOn == 0) {
            result.add("0:00");
            return;
        }
        String realTime = getTime(curTime, time);
        if (realTime == null) {
            return;
        }
        if (curTime.size() == turnedOn) {
            result.add(realTime);
            return;
        }
        if (curIndex >= time.length) {
            return;
        }
        // 选择
        curTime.add(curIndex);
        // 进入下一轮
        getBinaryTime(turnedOn, time, curTime, curIndex + 1, result);
        // 撤销选择
        curTime.remove(curTime.size() - 1);

        getBinaryTime(turnedOn, time, curTime, curIndex + 1, result);

    }

    private static String getTime(List<Integer> curTime, int[] time) {
        if (curTime.isEmpty()) {
            return "0:00";
        }
        int hour = 0;
        int minutes = 0;
        for (int i = 0; i < curTime.size(); i++) {
            Integer index = curTime.get(i);
            if (index <= 3) {
                hour += time[index];
            } else if (index <= 9) {
                minutes += time[index];
            }
        }
        if (hour >= 12 || minutes >= 60) {
            return null;
        }
        String hourStr = String.valueOf(hour);
        String minutesStr = String.valueOf(minutes);
        if (minutesStr.length() < 2) {
            minutesStr = "0" + minutesStr;
        }
        return hourStr + ":" + minutesStr;
    }

    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Integer> curPath = new ArrayList<>();
        int curSum = 0;
        solvePathSum(result, curPath, curSum, targetSum, root);
        return result;
    }

    private static void solvePathSum(List<List<Integer>> result, List<Integer> curPath, int curSum, int targetSum, TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null & root.right == null) {
            curSum += root.val;
            curPath.add(root.val);
            if (curSum == targetSum) {
                result.add(new ArrayList<>(curPath));
            }
            curPath.remove(curPath.size() - 1);
            return;
        }
        curSum += root.val;
        // 此处也可以直接 new 一个新的list来存储路径, 则后续无需 remove, 但是如果节点数量很多,则会存在大量空间的浪费
        curPath.add(root.val);
        solvePathSum(result, curPath, curSum, targetSum, root.left);
        solvePathSum(result, curPath, curSum, targetSum, root.right);
        curPath.remove(curPath.size() - 1);
    }

    public static int pathSumIII(TreeNode root, int targetSum) {


        return 0;
    }

    public static List<String> findStrobogrammatic(int n) {
        int left = 0;
        int right = n - 1;
        char[] curNum = new char[n];
        List<String> result = new ArrayList<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('6', '9');
        map.put('0', '0');
        map.put('1', '1');
        map.put('8', '8');
        map.put('9', '6');
        solveFindStrobogrammatic(result, curNum, n, left, right, map);
        return result;
    }

    private static void solveFindStrobogrammatic(List<String> result, char[] curNum, int n, int left, int right, Map<Character, Character> map) {
        if (left > right) {
            result.add(String.valueOf(curNum));
            return;
        }
        for (Character c : map.keySet()) {
            curNum[left] = c;
            if (left != right) {
                if (left == 0 && c == '0') {
                    continue;
                }
                curNum[right] = map.get(c);
            } else {
                if (c == '6' || c == '9') {
                    continue;
                }
            }
            solveFindStrobogrammatic(result, curNum, n, left + 1, right - 1, map);
        }
    }

    public static int strobogrammaticInRange(String low, String high) {
        int count = 0;
        long lowNum = Long.parseLong(low);
        long highNum = Long.parseLong(high);
        for (int i = low.length(); i <= high.length(); i++) {
            List<String> list = findStrobogrammatic(i);
            if (i == low.length() || i == high.length()) {
                for (String s : list) {
                    long num = Long.parseLong(s);
                    if (num >= lowNum && num <= highNum) {
                        count++;
                    }
                }
            } else {
                count += list.size();
            }
        }
        return count;
    }

    public static List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        boolean pass = isPass(n);
        if (pass) {
            return result;
        }
        List<Integer> curFactors = new ArrayList<>();
        int startIndex = 2;
        solveGetFactors(result, n, curFactors, startIndex);
        return result;
    }

    private static boolean isPass(int n) {
        boolean pass = true;
        for (int i = 2; i < n / 2 + 1; i++) {
            if (n % i == 0) {
                pass = false;
                break;
            }
        }
        return pass;
    }

    private static void solveGetFactors(List<List<Integer>> result, int n, List<Integer> curFactors, int startIndex) {
        if (n == 1) {
            if (curFactors.size() > 1) {
                result.add(new ArrayList<>(curFactors));
            }
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            if (n % i != 0) {
                continue;
            }
            curFactors.add(i);
            solveGetFactors(result, n / i, curFactors, i);
            curFactors.remove(curFactors.size() - 1);
        }
    }

    public static List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        int left = 0;
        List<String> curList = new ArrayList<>();
        solvePartition(result, curList, left, s);
        return result;
    }

    private static void solvePartition(List<List<String>> result, List<String> curList, int left, String s) {
        if (left == s.length()) {
            result.add(new ArrayList<>(curList));
            return;
        }
        for (int i = left; i < s.length(); i++) {
            boolean check = checkPalindrome(left, i, s);
            if (check == false) {
                continue;
            }
            curList.add(s.substring(left, i + 1));
            solvePartition(result, curList, i + 1, s);
            curList.remove(curList.size() - 1);
        }
    }

    private static boolean checkPalindrome(int left, int right, String s) {
        if (left > right || left < 0 || right < 0 || left >= s.length() || right >= s.length()) {
            return false;
        }
        if (left == right) {
            return true;
        }
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
